2622. Cache With Time Limit

解題程式碼

var TimeLimitedCache = function () {
  this.caches = new Map();
};

/**
 * @param {number} key
 * @param {number} value
 * @param {number} duration time until expiration in ms
 * @return {boolean} if un-expired key already existed
 */
TimeLimitedCache.prototype.set = function (key, value, duration) {
  const existValue = this.caches.get(key);
  if (existValue) {
    clearTimeout(existValue.timeId);
  }

  const timeId = setTimeout(() => {
    this.caches.delete(key);
  }, duration);
  this.caches.set(key, { value, timeId });

  return !!existValue;
};

/**
 * @param {number} key
 * @return {number} value associated with key
 */
TimeLimitedCache.prototype.get = function (key) {
  if (this.caches.has(key)) return this.caches.get(key).value;
  return -1;
};

/**
 * @return {number} count of non-expired keys
 */
TimeLimitedCache.prototype.count = function () {
  return this.caches.size;
};

解題思路、演算法

這題會實作具有時間限制快取的類別函式，get() 和 count() 相當簡單，就不多提。

set() 函式在題目中提到其回傳值是 key 對應的值有沒有存在快取，然後回傳一個布林值，所以宣告一個 existValue 變數給它，用 existValue 作函式回傳的結果，並且因為有搭配到 setTimeout 的使用，如果要重設同一個 key 的值，要先清除先前的 timeId，避免重設前的 timeout 觸發去將重設 key 之後的 value 清除。

接著就是設定 setTimeout，時間到時就清除已經存在快取的 key、value。

解法的時間、空間複雜度

參考資料

Cache With Time Limit - Leetcode 2622 - JavaScript 30-Day Challenge

2623. Memoize

解題程式碼

function memoize(fn) {
  let cache = new Map();

  return function (...args) {
    const strArgs = JSON.stringify(args);
    if (cache.has(strArgs)) {
      return cache.get(strArgs);
    }
    let returnValue = fn(...args);
    cache.set(strArgs, returnValue);
    return returnValue;
  };
}

解題思路、演算法

這題可以參考我鐵人賽的文章 Day22-了解 Memoization 機制，我用 Map 去儲存每次呼叫函式時的參數和計算結果，所以如果有相同的參數時，就可以直接從 Map 取出來而不用再重複運行函式。

要記得將參數做字串化再存在 Map，避免比較參數時因為 by reference 的特性，導致兩個相同的陣列參數(ex: [1, 2] 和 [1, 2])卻被判定不同的情況。

解法的時間、空間複雜度

時間複雜度: 不一定
空間複雜度: O(n)

2625. Flatten Deeply Nested Array

解題程式碼

var flat = function (arr, n) {
    const flattened = [];
    if (n === 0) return arr;

    arr.forEach((ele) => {
        if (!Array.isArray(ele)) {
            flattened.push(ele);
        } else {
            flattened.push(...flat(ele, n - 1));
        }
    })
    return flattened;
};

解題思路、演算法

就是考陣列扁平化，第二個參數是扁平的層數，用遞迴處理即可解決

解法的時間、空間複雜度

時間複雜度: O(1)
空間複雜度: O(1)

其他-無限層數

const arr = [1, 2, [3, 4], [5, 6, [7, 8]]];

const flat = (arr, initVal) => {
  const startVal = initVal || [];
  return arr.reduce((prevRes, item) => {
    if (Array.isArray(item)) {
      return flat(item, prevRes);
    } else {
      return prevRes.concat(item);
    }
  }, startVal);
};

const arr = [1, 2, [3, 4], [5, 6, [7, 8]]];
const flatArr = flat(arr);

console.log(flatArr); // [1, 2, 3, 4, 5, 6, 7, 8]

其他解法:

var arr = [[1, 2, 2], [3, 4, 5, 5], [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10];

// 解法1
Array.from(new Set(arr.flat(Infinity))).sort((a, b) => {
  return a - b;
});

// 解法2
function flatten(arr) {
  while (arr.some((item) => Array.isArray(item))) {
    arr = [].concat(...arr);
  }

  return arr;
}

Array.from(new Set(flatten(arr))).sort((a, b) => {
  return a - b;
});